package offer2

/**
原题链接:
https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof/

剑指offer 59_2.队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，
要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1

定义一个队列, 并实现函数 max_value 的到队列里的最大值

示例 1：
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：
输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]


限制：
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5
*/

type MaxQueue struct {
	queue []int
	max   []int
}

func Constructor59_2() MaxQueue {
	return MaxQueue{
		make([]int, 0),
		make([]int, 0),
	}
}

func (q *MaxQueue) Max_value() int { // 获取最大值
	if len(q.max) == 0 {
		return -1
	}
	return q.max[0]
}

// Push_back 添加值
// queue直接添加即可  maxQueue需要比较队尾元素,
// 如果比队尾元素大, 那么添加该元素
// 如果比队尾元素小, 那么添加队尾元素
func (q *MaxQueue) Push_back(value int) {
	q.queue = append(q.queue, value)                     //正常队列直接添加即可
	for len(q.max) != 0 && value > q.max[len(q.max)-1] { //只要max队列有元素, && value > 队尾元素
		q.max = q.max[:len(q.max)-1] //弹出队尾元素
	}
	q.max = append(q.max, value) //加入value
}

func (q *MaxQueue) Pop_front() int { // 移除队首元素
	n := -1
	if len(q.queue) != 0 {
		n = q.queue[0]
		q.queue = q.queue[1:]
		if q.max[0] == n {
			q.max = q.max[1:]
		}
	}
	return n
}
